The present invention relates to the encoding of a pictorial or textual image to provide image data for transmission and storage and the decoding of such image data to reconstruct the image. More particularly, the present invention relates to the hierarchal encoding of such images to provide sequential image data representing progressively improved approximations of the image and the decoding of such hierarchal image data.
Hierarchal encoding of images is known and has been proposed as an alternative to conventional line-by-line image encoding techniques for the transmission of images over communication channels of restricted bandwidth. Using hierarchal encoding, data corresponding to gross approximations of an image are transmitted first, followed by data corresponding to more refined approximations until the final image is transmitted. Therefore, the quality of the reconstructed image at the receiver is progressively improved as more image data is received.
One of the principal advantages of progressive image transmission using hierarchal encoding is the early recognition of the received image before transmission of the final image is completed. This is so because in many instances an early coarse approximation of an image is sufficient to permit identification of what is contained in the final image.
Related to early recognition of the transmitted image is the possibility of reducing the amount of data required for the transmission of an image. By aborting the transmission after receiving a satisfactory approximation of the image but before transmission of the final image is completed, the amount of data required for the transmission of the image is effectively reduced.
Hierarchal encoding of images is typically implemented by processing the information in an image to generate an explicit pyramidal data structure. Such a data structure contains multiple levels, each representing a successive approximation of the final image with the lowest level at the base of the pyramid representing the final image. Transmission of the pyramidal data structure begins at the highest level, i.e., at the vertex of the pyramid, followed by the transmission of successive lower levels.
Known techniques for implementing hierarchal encoding of images to obtain pyramidal data structures are described in U.S. Pat. No. 4,222,076 to Knowlton and U.S. Pat. No. 4,698,689 to Tzou. The Knowlton technique uses a look-up table based algorithm to format spatial domain gray-scale values of pixels into a pyramidal structure, each formatted value being the approximate average of paired gray-scale values. The Tzou technique takes the two-dimension transform of block encoded gray-scale values of pixels and quantizes the transform coefficients to obtain a pyramidal data structure.
The encoding and decoding functions used in Knowlton and Tzou require large computational and storage overhead for their implementation. Such overhead becomes a serious drawback when it is desired to implement a complete image coder-decoder (CODEC) as an integrated circuit, since the fabrication yield of such an integrated circuit decreases rapidly as the complexity or size of the circuit is increased. Therefore, a need clearly exists for a hierarchal, spatial domain image encoding and decoding technique using relatively simple encoding and decoding functions which do not require complex circuits, extensive computations or look-up tables for their implementation. Furthermore, a need exists for a hierarchal image encoding and decoding technique which provides high noise immunity and high data compression ratio, even without prematurely aborting the hierarchal transmission, when used in conjunction with an appropriate data compression output encoding technique, such as variable length encoding.